Hoppa till innehållet

Inducerad delgraf

Från Wikipedia
En bild som visar övergången från G till D
Vänstergraf är och högergraf är

Inom grafteorin är en inducerad delgraf en graf som består av en delmängd av en graf :s hörnmängd med tillhörande kantmängd.

Låt vara en godtycklig graf, och låt . Då är den inducerad delgrafen grafen vars hörnmängd med och kantmängder sådana att och .